package com.yww.leetcode.heap;

import com.yww.datastructure.heap.Heap;

/**
 * @author yww
 * @description 295. 数据流的中位数
 * @since 2024/2/7 22:02
 */
public class MedianFinder295 {
    // 大顶堆，支持扩容
    Heap left = new Heap(true, 10);
    // 小顶堆，支持扩容
    Heap right = new Heap(false, 10);

    public MedianFinder295() {

    }

    /**
     * 为了保证两边数据量的平衡
     * <ul>
     * <li>两边数据一样时,加入左边</li>
     * <li>两边数据不一样时,加入右边</li>
     * </ul>
     * 但是, 随便一个数能直接加入吗?
     * <ul>
     * <li>加入左边前, 先将num加入右小堆，然后应该挑右边最小的加入</li>
     * <li>加入右边前, 先将num加入左大堆，然后应该挑左边最大的加入</li>
     * </ul>
     */
    public void addNum(int num) {
        if (left.size() == right.size()) {
            right.offer(num);
            int rightTop = right.poll();
            left.offer(rightTop);
        } else {
            left.offer(num);
            int leftTop = left.poll();
            right.offer(leftTop);
        }
    }

    /**
     * <ul>
     *     <li>两边数据一致, 左右各取堆顶元素求平均</li>
     *     <li>左边多一个, 取左边元素</li>
     * </ul>
     */

    public double findMedian() {
        if (left.size() == right.size()) {
            return (left.peek() + right.peek()) / 2.0;
        } else {
            return left.peek();
        }
    }
}
